"""
插入排序
"""


def insert_Sort(target_List: list):
    for index in range(1, len(target_List)):   # 从列表第二元素开始遍历
        temp = target_List[index]   # 记录需插入值为temp
        pos = index - 1   # 用pos指示插入位置，默认0
        while pos >= 0 and temp < target_List[pos]:
            # 插入位置合法 且 插入值temp比插入位置原值data[i]更小，插入位置不合适
            # 把pos元素后移一位，覆写index位置值，原值存储在temp
            target_List[pos + 1] = target_List[pos]
            pos -= 1    # 插入位置前移
        # 此时插入位置合适，因为插入值temp大于当前位置值，此时在后一位执行插入
        target_List[pos + 1] = temp  # 插入temp到后一位


# 示例
data = [9, 15, 31, -4, 0, 94, -25, 16, 27]
insert_Sort(data)
print(data)
# 结果如下
# [-25, -4, 0, 9, 15, 16, 27, 31, 94]
